Efficient Tabling of Structured Data with Enhanced Hash-Consing

摘要

Current tabling systems suffer from an increase in space complexity, timecomplexity or both when dealing with sequences due to the use of datastructures for tabled subgoals and answers and the need to copy terms into andfrom the table area. This symptom can be seen in not only B-Prolog, which useshash tables, but also systems that use tries such as XSB and YAP. In thispaper, we apply hash-consing to tabling structured data in B-Prolog. Whilehash-consing can reduce the space consumption when sharing is effective, itdoes not change the time complexity. We enhance hash-consing with twotechniques, called input sharing and hash code memoization, for reducing thetime complexity by avoiding computing hash codes for certain terms. Theimproved system is able to eliminate the extra linear factor in the old systemfor processing sequences, thus significantly enhancing the scalability ofapplications such as language parsing and bio-sequence analysis applications.We confirm this improvement with experimental results.